
/**
 * 
 * 合并两个排序的链表
 * 
 * 描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围： 
0
≤
n
≤
1000
0≤n≤1000，
−
1000
≤
节
点
值
≤
1000
−1000≤节点值≤1000
要求：空间复杂度 
O
(
1
)
O(1)，时间复杂度 
O
(
n
)
O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：


或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

示例1

输入：
{1,3,5},{2,4,6}
复制
返回值：
{1,2,3,4,5,6}
复制
示例2

输入：
{},{}
复制
返回值：
{}
复制
示例3

输入：
{-1,2,4},{1,3,4}
复制
返回值：
{-1,1,2,3,4,4}
复制
 */
public class 合并两个排序的链表 {
    

    public static void main(String[] args) {
        

        ListNode node1 = new ListNode(-1);
        node1.next = new ListNode(2);
        node1.next.next = new ListNode(4);
        
        ListNode node2 = new ListNode(1);
        node2.next = new ListNode(3);
        node2.next.next = new ListNode(4);

        ListNode pre = mergeTwoLists(node1, node2);

        System.out.println(pre.toString());

    }

    private static ListNode mergeTwoLists(ListNode pHead1, ListNode pHead2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;

        while (pHead1!= null && pHead2!= null) {
            if (pHead1.val < pHead2.val) {
                curr.next = pHead1;
                pHead1 = pHead1.next;
            } else {
                curr.next = pHead2;
                pHead2 = pHead2.next;
            }
            curr = curr.next;
        }

        if (pHead1!= null) {
            curr.next = pHead1;
        } else {
            curr.next = pHead2;
        }

        return dummy.next;
    }

    private static class ListNode{

        public int val;
        public ListNode next;

        public ListNode(int val){

            this.val = val;
        }

        public String toString(){

            StringBuilder builder = new StringBuilder();

            builder.append(val);
            builder.append(",");

            ListNode nextNode = next;

            while(null!=nextNode){

                builder.append(nextNode.val);
                builder.append(",");
                nextNode = nextNode.next;
            }
            

            return builder.toString();
        }

    }
}
